package com.bang.study.day02;

import com.bang.study.day01.InsertionSort;
import com.bang.study.util.ArrayUtil;
import com.bang.study.util.TestUtil;
import org.apache.commons.lang3.ArrayUtils;

/**
 * @Auther: Bang
 * @Date: 2019/9/21 0021 10:18
 * @Description: 三路快速排序
 * @link https://www.cnblogs.com/deng-tao/p/6536302.html
 * @描述:
 */
public class QuickSortV4 {


    /**
     * 快速排序
     *
     * @param arr
     */
    public static void sort(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 对数组arr[l,r]快速排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSort(Integer[] arr, int l, int r) {
        if (r - l <= 16) {
            InsertionSort.insertSort(arr, l, r);
        } else {
            // partition
            swap(arr, l, (int) Math.random() * (r - l + 1) + l);
            int p = arr[l];

            int lt = l; // arr[l+1 ... lt] < v
            int i = l + 1; // arr[lt+1 ... i-1) == v
            int gt = r + 1; // arr[gt...r] > v
            while (i < gt){
                if (arr[i] > p) {
                    swap(arr, i, gt - 1);
                    gt--;
                }else if (arr[i]<p){
                    swap(arr, i, lt + 1);
                    lt++;
                    i++;
                }else {
                    i++;
                }
            }
            swap(arr, l, lt);

            quickSort(arr, l, lt - 1);
            quickSort(arr, gt, r);
        }
    }


    private static void swap(Integer[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] array = ArrayUtil.generateRandomArray(1000000, 0, 20);
        TestUtil.test(MergeSort.class, ArrayUtils.clone(array));

        ArrayUtil.printArray(array, 10);
        long start = System.nanoTime();
        sort(array);
        long end = System.nanoTime();
        double v = (end - start) / 1000000000.0;
        System.out.println(String.format("耗时: %s 秒", v));
        ArrayUtil.printArray(array, 10);

    }
}
